package hash;


public class MyHashMap {
    static class Node {
        //使用Node类来表示链表中的节点
        public Node next;
        int value;
        int key;

        public Node(int value, int key) {
            this.value = value;
            this.key = key;
        }
    }

    private Node[] table = new Node[1000];//哈希表数组
    private int size = 0;//哈希表大小

    //设定哈希函数，把key映射到数组下标
    private int hashcode(int key) {
        return key % table.length;
    }

    //哈希表的核心操作
    //插入修改键值对
    public void put(int key, int value) {
        //根据key计算下标位置
        int index = hashcode(key);
        //2遍历链表，查找key是否存在
        //如果不存在，直接插入，，如果存在，修改value
        Node head = table[index];
        for (Node cur = head; cur != null; cur = cur.next) {
            if (cur.key == key) {
                cur.value = value;
                return;
            }
        }
        //3如果不存在，直接插入，按照头插的方式
        Node newNode = new Node(key, value);
        newNode.next = head;
        table[index] = newNode;
        size++;
        //扩容
        if ((double) size / table.length > 0.75) {
            resize();
        }
    }

    private void resize() {
        Node[] newTable = new Node[table.length * 2];
        for (int i = 0; i < table.length; i++) {
            for (Node cur = table[i]; cur != null; cur = cur.next) {
                Node newNode = new Node(cur.key, cur.value);
                int newIndex = cur.key % newTable.length;
                newNode.next = newTable[newIndex];
                newTable[newIndex] = newNode;
            }
        }
        table = newTable;
    }

    //根据键获取值
    public Integer get(int key) {
        int index = hashcode(key);
        for (Node cur = table[index]; cur != null; cur = cur.next) {
            if (cur.key == key) {
                return cur.value;
            }
        }
        return null;
    }

    //删除键值对
    public void remove(int key) {
        int index = hashcode(key);
        Node head = table[index];
        if (head == null) {
            return;
        }
        if (head.key == key) {
            table[index] = head.next;
            size--;
            return;
        }
        Node prev = head;
        Node cur = head.next;
        while (cur != null) {
            if (cur.key == key) {
                prev.next = cur.next;
                size--;
                return;
            }
            prev = cur;
            cur = cur.next;
        }
    }
}
